package matrix;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * @author kaho
 * @since 2020/12/26
 */
public class _84_柱状图中最大的矩形 {

    /**
     * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
     * <p>
     * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
     *
     * @param heights
     * @return
     */
    public int largestRectangleArea(int[] heights) {
        if (heights.length == 0) {
            return 0;
        }
        if (heights.length == 1) {
            return heights[0];
        }

        int res = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < heights.length; i++) {
            while (!stack.isEmpty() && heights[stack.peekLast()] > heights[i]) {
                int curHigh = heights[stack.pollLast()];
                while (!stack.isEmpty() && curHigh == heights[stack.peekLast()]) {
                    stack.pollLast();
                }
                int wid;
                if (stack.isEmpty()) {
                    wid = i;
                } else {
                    wid = i - stack.peekLast() - 1;
                }
                res = Math.max(res, wid * curHigh);
            }
            stack.addLast(i);
        }

        while (!stack.isEmpty()) {
            int curHigh = heights[stack.pollLast()];
            while (!stack.isEmpty() && curHigh == heights[stack.peekLast()]) {
                stack.pollLast();
            }
            int wid;
            if (stack.isEmpty()) {
                wid = heights.length;
            } else {
                wid = heights.length - stack.peekLast() - 1;
            }
            res = Math.max(res, wid * curHigh);
        }
        return res;
    }


    /**
     * 哨兵解法
     * @param heights
     * @return
     */
    public int largestRectangleArea1(int[] heights) {
        if (heights.length == 0) {
            return 0;
        }
        if (heights.length == 1) {
            return heights[0];
        }

        int[] newHeights = new int[heights.length+2];
        System.arraycopy(heights, 0, newHeights,1,heights.length);
        int res = 0;
        Deque<Integer> stack = new ArrayDeque<>(newHeights.length);
        stack.addLast(0);
        for (int i = 1; i < newHeights.length; i++) {
            while (newHeights[stack.peekLast()] > newHeights[i]){
                int curHeight = newHeights[stack.pollLast()];
                int width = i - stack.peekLast() - 1;
                res = Math.max(res, curHeight*width);
            }
            stack.addLast(i);
        }
        return res;
    }
}
